#include <iostream>
#include <vector>
using namespace std;

void hoareSort(vector<int> &nums, int left, int right)
{
    if (left >= right)
    {
        return;
    }

    // 选择key
    int key = nums[left];
    // 把key放入指定的位置
    int begin = left;
    int end = right;
    int keyi = left;

    while (begin < end)
    {
        while (nums[end] > nums[keyi])
        {
            end--;
        }
        while (nums[begin] > nums[keyi])
        {
            begin++;
        }
        swap(nums[begin], nums[end]);
    }
    // keyi 并没有进行交换
    swap(nums[keyi], nums[begin]);

    hoareSort(nums, left, begin - 1);
    hoareSort(nums, begin + 1, right);
}
vector<int> tmp;
void mergeSort(vector<int> &nums, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);

    // 合并两个有序数组
    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right)
    {
        tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
    }
    while (cur1 <= mid)
    {
        tmp[i++] = nums[cur1++];
    }
    while (cur2 <= right)
    {
        tmp[i++] = nums[cur2++];
    }
    // 从tmp中还原出数组
    for (int i = left; i <= right; ++i)
    {
        nums[i] = tmp[i - left];
    }
}

// 选择排序
void selectSort(vector<int> &nums)
{
    // 单次寻找最小的
    int size = nums.size();
    // 遍历数组
    for (int j = 0; j < size; ++j)
    {
        int maxNum = 0;
        for (int i = 0; i < size - j; ++i)
        {
            if (nums[i] > nums[maxNum])
            {
                maxNum = i;
            }
        }
        // 到这里是找到最大元素的下标
        // 与最后的元素交换
        swap(nums[maxNum], nums[size - j - 1]);
    }
}
void bubbleSort(vector<int> &nums)
{
    // 冒泡排序的思想，第一轮找到一个最大的，放在size - 1位置 ，第二轮找到剩余最小的，放在size - 2 位置
    // 先选择一轮
    int size = nums.size();
    for (int j = 0; j < size; ++j)
    {
        for (int i = 0; i < size - j; ++i)
        {
            if (nums[i] > nums[size - 1 - j])
            {
                swap(nums[i], nums[size - 1 - j]);
            }
        }
    }
}
void insertSort(vector<int> &nums)
{
    // 选择一个数，插入到前面的有序数组中
    for (int i = 1; i < nums.size(); ++i)
    {
        int end = i;
        int x = nums[i];
        // 往前面寻找
        while (end >= 0)
        {
            if (nums[end] > x)
            {
                nums[end + 1] = nums[end];
                end--;
            }
            else
            {
                break;
            }
        }
        // 此时的nums[end] 可能为 == x 或者小于 x
        nums[end + 1] = x;
    }
}
void shellSort(vector<int> &nums)
{
    int gap = 3;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int j = 0; j < gap; ++j)
        {
            for (int i = j + gap; i < nums.size(); i += gap)
            {
                int end = i - gap;
                int x = nums[i];
                while (end >= 0)
                {
                    if (nums[end] > x)
                    {
                        nums[end + gap] = nums[end];
                        end -= gap;
                    }
                    else
                    {
                        break;
                    }
                }
                nums[end + gap] = x;
            }
        }
    }
}
//升序，建大堆
void AdjustDown(std::vector<int>& a,int n,int parent)
{
    int child = parent * 2 + 1;
    while (child < n)
    {
        //找到两个孩子中最小的一个的下标
        if (child + 1 < n && a[child] < a[child + 1])
        {
            child++;
        }
        if (a[child] > a[parent])
        {
            std::swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }	
}
void heapSort(vector<int>& nums)
{
    //建堆
    int n = nums.size();
    //1.建堆,采用向下调整建堆，找出第一个非空叶子节点
    for(int i = (n - 2) / 2;i >= 0;i--)
    {
        AdjustDown(nums,nums.size(),i);
    }
    for(int i = n - 1;i>= 0;i--)
    {
        //进行交换，然后再进行调整，交换到最后的元素就已经排好序了
        swap(nums[0],nums[i]);
        AdjustDown(nums,i,0);
    }

}
int main()
{
    vector<int> nums;
    nums.push_back(5);
    nums.push_back(4);
    nums.push_back(6);
    nums.push_back(9);
    nums.push_back(2);
    nums.push_back(7);
    nums.push_back(1);

    tmp.resize(nums.size());
    // hoareSort(nums,0,nums.size() - 1);
    // mergeSort(nums, 0, nums.size() - 1);
    // selectSort(nums);
    // bubbleSort(nums);
    // insertSort(nums);
    // shellSort(nums);
    heapSort(nums);
    
    for (auto num : nums)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}